package com.atcumt.baidu;


/**
 * 牧尘青灯  11:46
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 *
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 */
public class BD001 {
    public void flatten(TreeNode root) {
        while (root != null) {
            TreeNode node = root.left;
            if (node != null) {
                while (node.right != null) {
                    node = node.right;
                }
                node.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    }

    /**
     * root = [1,2,5,3,4,null,6]
     *     1
     *   2   5
     * 3  4  n 6
     * @param args
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);

        new BD001().flatten(root);
        while (root != null) {
            System.out.print(root.val+ " ");
            root = root.right;
        }

    }


}
